W8. Sequences, Series, Linear Recurrence

Author

Zakhar Podyakov

Published

October 29, 2025

Quiz | Flashcards

1. Summary

1.1 Introduction to Sequences

A sequence is an ordered list of numbers. Formally, it’s a function that maps a subset of natural numbers (like \({0, 1, 2, ...}\) or \({1, 2, 3, ...}\)) to a set of values. Each element in the sequence is called a term. We often denote a sequence by \({a_n}\), where \(a_n\) is the term at position \(n\).

1.1.1 Arithmetic Progression

An arithmetic progression is a sequence where the difference between consecutive terms is constant. This constant difference is called the common difference, denoted by \(d\).

  • Formula: \(a_n = a_0 + nd\)
  • Example: The sequence \(-10, -5, 0, 5, 10, ...\) is an arithmetic progression with an initial term \(a_0 = -10\) and a common difference \(d = 5\).
1.1.2 Geometric Progression

A geometric progression is a sequence where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio, denoted by \(t\).

  • Formula: \(a_n = a_0 \cdot t^n\)
  • Example: The sequence \(1, -2, 4, -8, 16, ...\) is a geometric progression with an initial term \(a_0 = 1\) and a common ratio \(t = -2\).
1.2 Recursively Defined Sequences

A sequence is defined recursively if the definition of a term depends on previous terms. This definition requires one or more initial conditions to start the sequence.

  • Recursion or recurrence happens when the definition of a concept or process depends on a simpler version of itself.
  • Example: The Fibonacci sequence is defined recursively.
    • Recursive Definition: \(f_0 = 0\), \(f_1 = 1\), and \(f_{n+2} = f_{n+1} + f_n\) for \(n \ge 0\).
    • List of Terms: \(0, 1, 1, 2, 3, 5, 8, ...\)
    • Each term (after the first two) is the sum of the two preceding ones.
1.3 Series

A series is the sum of the terms of a sequence.

1.3.1 Summation (Sigma Notation)

We use sigma notation (\(\sum\)) to represent the sum of terms.

  • Notation: \(S(n) = \sum_{i=m}^{n} a_i = a_m + a_{m+1} + \dots + a_n\)
    • \(i\) is the index of summation.
    • \(m\) is the lower limit.
    • \(n\) is the upper limit.
  • Recursive Definition: \(S(m) = a_m\) and \(S(n+1) = S(n) + a_{n+1}\).
1.3.2 Multiplication (Pi Notation)

We use pi notation (\(\prod\)) to represent the product of terms.

  • Notation: \(P(n) = \prod_{i=m}^{n} a_i = a_m \cdot a_{m+1} \cdot \dots \cdot a_n\)
  • Example (Factorial): \(n! = \prod_{i=1}^{n} i = 1 \cdot 2 \cdot \dots \cdot n\).
    • By definition, \(0! = 1\).
    • Recursive Definition: \(1! = 1\) and \((n+1)! = (n+1) \cdot n!\).
1.3.3 Arithmetic Series

An arithmetic series is the sum of the terms of an arithmetic progression.

  • Formula: \(\sum_{i=0}^{n} (a_0 + id) = (n+1)a_0 + d \frac{n(n+1)}{2}\)
1.3.4 Geometric Series

A geometric series is the sum of the terms of a geometric progression.

  • Formula: For \(t \neq 1\), \(\sum_{i=0}^{n} a_0 t^i = a_0 \frac{t^{n+1}-1}{t-1}\)
1.4 Linear Recurrence Sequences

A linear recurrence sequence is a sequence where each term is a linear combination of a fixed number of previous terms. A sequence \(\{a_n\}\) is a linear recurrence of order \(k\) if: \[a_{n+k} = t_1 a_{n+k-1} + t_2 a_{n+k-2} + \dots + t_k a_n\] where \(t_1, t_2, \dots, t_k\) are fixed coefficients.

1.4.1 Solving Linear Recurrence Sequences

The goal is to find a non-recursive or closed-form formula for \(a_n\).

  • Algorithm for Second-Order Recurrences A second-order linear recurrence has the form \(a_{n+2} - t_1 a_{n+1} - t_2 a_n = 0\).
    1. Find the Characteristic Equation: Replace \(a_{n+i}\) with \(\lambda^i\) to get the characteristic equation: \[\chi(\lambda) = \lambda^2 - t_1 \lambda - t_2 = 0\]
    2. Find the Roots: Solve the quadratic equation for its roots, \(p_1\) and \(p_2\).
    3. Determine the General Solution:
      • Case 1: Distinct Roots (\(p_1 \neq p_2\)): The general solution is: \[a_n = c_1 \cdot p_1^n + c_2 \cdot p_2^n\]
      • Case 2: Repeated Roots (\(p_1 = p_2 = p\)): The general solution is: \[a_n = (c_1 \cdot n + c_2) \cdot p^n\]
    4. Find the Constants: Use the initial conditions (e.g., values for \(a_0\) and \(a_1\)) to create a system of two linear equations and solve for the constants \(c_1\) and \(c_2\).
  • Example 1: Distinct Roots Solve \(a_{n+2} = 3a_{n+1} - 2a_n\) with \(a_0 = 1, a_1 = 3\).
    1. Characteristic Equation: \(\lambda^2 - 3\lambda + 2 = 0\).
    2. Roots: \((\lambda-1)(\lambda-2) = 0\), so \(p_1 = 1\) and \(p_2 = 2\).
    3. General Solution: \(a_n = c_1(1)^n + c_2(2)^n = c_1 + c_2 2^n\).
    4. Find Constants:
      • For \(n=0\): \(a_0 = 1 = c_1 + c_2(2^0) \implies 1 = c_1 + c_2\).
      • For \(n=1\): \(a_1 = 3 = c_1 + c_2(2^1) \implies 3 = c_1 + 2c_2\).
      • Solving the system gives \(c_2 = 2\) and \(c_1 = -1\).
    • Final Solution: \(a_n = -1 + 2 \cdot 2^n = 2^{n+1} - 1\).
  • Example 2: Repeated Roots Solve \(a_{n+2} = 4a_{n+1} - 4a_n\) with \(a_0 = 2, a_1 = 1\).
    1. Characteristic Equation: \(\lambda^2 - 4\lambda + 4 = 0\).
    2. Roots: \((\lambda-2)^2 = 0\), so \(p_1 = p_2 = 2\).
    3. General Solution: \(a_n = (c_1 n + c_2) \cdot 2^n\).
    4. Find Constants:
      • For \(n=0\): \(a_0 = 2 = (c_1(0) + c_2) \cdot 2^0 \implies 2 = c_2\).
      • For \(n=1\): \(a_1 = 1 = (c_1(1) + c_2) \cdot 2^1 \implies 1 = (c_1 + 2) \cdot 2 \implies c_1 = -1.5\).
    • Final Solution: \(a_n = (-1.5n + 2) \cdot 2^n\).
1.4.2 The Fibonacci Sequence

The Fibonacci sequence \(f_n\) is defined by \(f_{n+2} = f_{n+1} + f_n\) with \(f_0=0, f_1=1\).

  1. Characteristic Equation: \(\lambda^2 - \lambda - 1 = 0\).
  2. Roots: \(p_1 = \frac{1+\sqrt{5}}{2}\) (the golden ratio, \(\phi\)) and \(p_2 = \frac{1-\sqrt{5}}{2}\).
  3. General Solution: \(f_n = c_1 (\frac{1+\sqrt{5}}{2})^n + c_2 (\frac{1-\sqrt{5}}{2})^n\).
  4. Find Constants: Using \(f_0=0\) and \(f_1=1\), we find \(c_1 = \frac{1}{\sqrt{5}}\) and \(c_2 = -\frac{1}{\sqrt{5}}\).
  5. Final Solution (Binet’s Formula): \[f_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right)\]
1.5 Systems of Recurrence Sequences

Sometimes, sequences are defined in terms of each other. A system of recurrence relations can often be solved by converting it into a single higher-order recurrence relation.

  • Method:
    1. Start with a system, for example: \[a_{n+1} = a_n + b_n\] \[b_{n+1} = a_n - b_n\]
    2. Isolate one variable in one equation. From the first equation, \(b_n = a_{n+1} - a_n\).
    3. Substitute this into the other equation to eliminate that variable. To do this for \(b_{n+1}\), first shift the index: \(b_{n+1} = a_{n+2} - a_{n+1}\).
    4. Now substitute both expressions for \(b_n\) and \(b_{n+1}\) into the second equation: \[(a_{n+2} - a_{n+1}) = a_n - (a_{n+1} - a_n)\]
    5. Simplify to get a single recurrence relation: \(a_{n+2} = 2a_n\).
    6. Solve this new relation using the standard algorithm. You may need to compute initial values (like \(a_1\)) from the original system.

2. Definitions

  • Sequence: An ordered list of elements, typically numbers, defined by a function from the natural numbers to a set of values.
  • Arithmetic Progression: A sequence where the difference between any two consecutive terms is constant.
  • Geometric Progression: A sequence where the ratio between any two consecutive terms is constant.
  • Recursion: A method of defining something (like a function or sequence) in terms of itself.
  • Series: The sum of the terms in a sequence.
  • Arithmetic Series: The sum of the terms in an arithmetic progression.
  • Geometric Series: The sum of the terms in a geometric progression.
  • Linear Recurrence Sequence: A sequence where each term is a linear combination of a fixed number of preceding terms.
  • Characteristic Equation: An algebraic equation derived from a linear recurrence relation, whose roots are used to find the closed-form solution of the sequence.

3. Formulas

  • Arithmetic Progression: \(a_n = a_0 + nd\)
  • Geometric Progression: \(a_n = a_0 \cdot t^n\)
  • Second-Order Recurrence General Solution (Distinct Roots \(p_1, p_2\)): \(a_n = c_1 p_1^n + c_2 p_2^n\)
  • Second-Order Recurrence General Solution (Repeated Root \(p\)): \(a_n = (c_1 n + c_2) p^n\)

4. Examples

4.1. Solve Recurrence Sequences (Lab 7, Task 1)

Solve the following recurrence sequences.

  1. \(a_0 = 15, a_{n+1} = a_n - 4\)
  2. \(a_0 = -1, a_{n+1} = (-2)a_n\)
  3. \(a_0 = 1, a_1 = 3, a_{n+2} = 3a_{n+1} - 2a_n\)
  4. \(a_0 = 2, a_1 = 1, a_{n+2} = 4a_{n+1} - 4a_n\)
Click to see the solution

(a) Arithmetic Sequence: This is an arithmetic sequence with first term 15 and common difference -4.

  • Answer: \(a_n = 15 - 4n\).

(b) Geometric Sequence: This is a geometric sequence with first term -1 and common ratio -2.

  • Answer: \(a_n = -1 \cdot (-2)^n = -(-2)^n\).

(c) Linear Homogeneous Recurrence:

  • Characteristic equation: \(\lambda^2 - 3\lambda + 2 = 0 \implies (\lambda-1)(\lambda-2)=0\).
  • Roots are \(\lambda_1=1, \lambda_2=2\).
  • General solution: \(a_n = c_1(1)^n + c_2(2)^n\).
  • Use initial conditions:
    • \(n=0: a_0=1 = c_1 + c_2\).
    • \(n=1: a_1=3 = c_1 + 2c_2\).
  • Solving gives \(c_2=2, c_1=-1\).
  • Answer: \(a_n = 2^{n+1} - 1\).

(d) Linear Homogeneous Recurrence (Repeated Roots):

  • Characteristic equation: \(\lambda^2 - 4\lambda + 4 = 0 \implies (\lambda-2)^2=0\).
  • Repeated root \(\lambda=2\).
  • General solution: \(a_n = (c_1 + c_2n)(2)^n\).
  • Use initial conditions:
    • \(n=0: a_0=2 = (c_1 + 0)(1) \implies c_1=2\).
    • \(n=1: a_1=1 = (c_1 + c_2)(2) = (2+c_2)(2) \implies 1/2=2+c_2 \implies c_2 = -3/2\).
  • Answer: \(a_n = (2 - \frac{3}{2}n)2^n\).
4.2. Rewrite and Solve Systems of Recurrence Sequences (Lab 7, Task 2)

Rewrite recursively the following systems of recurrence sequences and solve (find a general solution).

  1. \(\begin{cases} a_{n+1} = 2a_n + b_n \\ b_{n+1} = a_n - b_n \end{cases}\)
  2. \(\begin{cases} a_{n+1} = a_n + 2b_n \\ b_{n+1} = 3a_n - 2b_n \end{cases}\)
Click to see the solution

(a) First System:

  1. From the first equation, \(b_n = a_{n+1} - 2a_n\).
  2. From the second equation, \(b_{n+1} = a_n - b_n\).
  3. Substitute \(b_n\): \(b_{n+1} = a_n - (a_{n+1} - 2a_n) = 3a_n - a_{n+1}\).
  4. From the first equation shifted by one index: \(a_{n+2} = 2a_{n+1} + b_{n+1}\).
  5. Substitute the expression for \(b_{n+1}\): \(a_{n+2} = 2a_{n+1} + (3a_n - a_{n+1}) = a_{n+1} + 3a_n\).
  6. The single recurrence is \(a_{n+2} - a_{n+1} - 3a_n = 0\).
  7. Characteristic equation: \(\lambda^2 - \lambda - 3 = 0\). Roots are \(\lambda = \frac{1 \pm \sqrt{13}}{2}\).
  8. General Solution: \(a_n = c_1(\frac{1+\sqrt{13}}{2})^n + c_2(\frac{1-\sqrt{13}}{2})^n\).

(b) Second System:

  1. From the first equation, \(2b_n = a_{n+1} - a_n \implies b_n = \frac{a_{n+1}-a_n}{2}\).
  2. From the first equation shifted by one index: \(a_{n+2} = a_{n+1} + 2b_{n+1}\).
  3. Substitute the second original equation: \(a_{n+2} = a_{n+1} + 2(3a_n - 2b_n) = a_{n+1} + 6a_n - 4b_n\).
  4. Substitute the expression for \(b_n\): \(a_{n+2} = a_{n+1} + 6a_n - 4(\frac{a_{n+1}-a_n}{2}) = a_{n+1} + 6a_n - 2a_{n+1} + 2a_n = -a_{n+1} + 8a_n\).
  5. The single recurrence is \(a_{n+2} + a_{n+1} - 8a_n = 0\).
  6. Characteristic equation: \(\lambda^2 + \lambda - 8 = 0\). Roots are \(\lambda = \frac{-1 \pm \sqrt{33}}{2}\).
  7. General Solution: \(a_n = c_1(\frac{-1+\sqrt{33}}{2})^n + c_2(\frac{-1-\sqrt{33}}{2})^n\).
4.3. Formulate a Recurrence Relation (Lab 7, Task 3)

Find the number of sequences of length \(n\) over the alphabet \(\{0,1,2\}\) that do not contain two consecutive zeros or two consecutive ones.

Click to see the solution
  1. Define Subproblems: Let \(a_n\) be the total number of such sequences. Let \(a_n^0, a_n^1, a_n^2\) be the number of valid sequences of length \(n\) ending with 0, 1, and 2, respectively.
  2. Formulate Relationships:
    • \(a_n = a_n^0 + a_n^1 + a_n^2\).
    • A sequence ending in 0 cannot be preceded by a 0. So it must be preceded by a 1 or a 2. Thus, \(a_n^0 = a_{n-1}^1 + a_{n-1}^2\).
    • A sequence ending in 1 cannot be preceded by a 1. So it must be preceded by a 0 or a 2. Thus, \(a_n^1 = a_{n-1}^0 + a_{n-1}^2\).
    • A sequence ending in 2 can be preceded by anything. Thus, \(a_n^2 = a_{n-1}^0 + a_{n-1}^1 + a_{n-1}^2 = a_{n-1}\).
  3. Combine to a Single Recurrence:
    • \(a_n = a_n^0 + a_n^1 + a_n^2 = (a_{n-1}^1 + a_{n-1}^2) + (a_{n-1}^0 + a_{n-1}^2) + a_{n-1}\).
    • \(= (a_{n-1}^0+a_{n-1}^1+a_{n-1}^2) + a_{n-1}^2 + a_{n-1} = a_{n-1} + a_{n-1}^2 + a_{n-1}\).
    • Since \(a_{n-1}^2 = a_{n-2}\), we have \(a_n = 2a_{n-1} + a_{n-2}\).
  4. Find Initial Conditions:
    • \(n=1\): “0”, “1”, “2”. Total \(a_1=3\).
    • \(n=2\): “01”, “02”, “10”, “12”, “20”, “21”, “22”. Total \(a_2=7\).
    • Check: \(a_2 = 2a_1 + a_0\). We need \(a_0\). Let’s define \(a_0=1\) (the empty string). Then \(a_2=2(3)+1=7\). Correct.
Answer: The recurrence relation is \(a_n = 2a_{n-1} + a_{n-2}\) with initial conditions \(a_0=1, a_1=3\).
4.4. Formulate a Recurrence for Password Combinations (Lab 7, Task 4)

A password is a combination of any of the ten digits 0-9, the 52 letters, and the eight special characters +, -, _, &, %, *, (, ). Any letter or special character has to be followed by a digit. Determine the number of possible passwords whose length is eight.

Click to see the solution
  1. Define Subproblems: Let \(a_n\) be the number of valid passwords of length \(n\). To find a recurrence, we consider how a valid password of length \(n\) can be formed.
  2. Case Analysis:
    • Case 1: The password ends with a digit. A password of length \(n\) ending with a digit can be formed by taking any valid password of length \(n-1\) and appending one of the 10 digits. Number of ways: \(10 \cdot a_{n-1}\).
    • Case 2: The password ends with a letter or special character. This is not possible. By the rules, a letter or special character must be followed by a digit. This means the last character can never be a letter or special character.
  3. Let’s redefine: Let \(D_n\) be the number of valid passwords of length \(n\) ending in a digit. Let \(L_n\) be the number of valid passwords of length \(n\) ending in a letter/special char.
    • The total is \(a_n = D_n + L_n\).
    • To get a string ending in a digit, we can append a digit to any valid string of length \(n-1\). So \(D_n = 10 \cdot a_{n-1} = 10(D_{n-1}+L_{n-1})\).
    • To get a string ending in a letter/special char (60 options), we can append it to any valid string of length \(n-1\) that ends in a digit. So \(L_n = 60 \cdot D_{n-1}\).
  4. Combine:
    • \(a_n = D_n + L_n = 10(D_{n-1}+L_{n-1}) + 60 D_{n-1} = 10 a_{n-1} + 60 D_{n-1}\). This is not a single recurrence yet.
    • Substitute \(D_{n-1} = 10 a_{n-2}\).
    • \(a_n = 10a_{n-1} + 60(10a_{n-2}) = 10a_{n-1} + 600a_{n-2}\).
  5. Initial Conditions:
    • \(a_1\): 10 digits + 60 letters/specials = 70.
    • \(a_2\): DD (1010), LD (6010). Total = 100+600=700.
    • Check: \(a_2 = 10a_1 + 600a_0\)? Let’s define \(a_0=1\) (empty password). Then \(a_2 = 10(70) + 600(1) = 700+600=1300\). Incorrect.
    • The issue is in \(D_n\). A digit can follow a digit or a letter/special. So \(D_n = 10(D_{n-1}+L_{n-1})\). Correct. A letter can only follow a digit. \(L_n = 60 D_{n-1}\). Correct. Ah, \(L_1\) is 60, \(D_1\) is 10. \(a_1=70\). \(D_2=10(a_1)=700\). \(L_2=60(D_1)=600\). \(a_2 = 1300\).
    • The recurrence is \(a_n = 10a_{n-1} + 600a_{n-2}\).
  6. Calculate \(a_8\):
    • \(a_1 = 70, a_2 = 1300\)
    • \(a_3 = 10(1300) + 600(70) = 13000 + 42000 = 55000\).
    • … This is tedious to do by hand.
Answer: The recurrence is \(a_n = 10a_{n-1} + 600a_{n-2}\) with \(a_1 = 70, a_2 = 1300\).
4.5. Formulate a Recurrence Relation (Lab 7, Task 5)

Formulate a recurrence relation and provide initial conditions for the number of ways to partition a segment of length \(n\) into segments of length 1, 2, and 3, such that there are no three consecutive segments of length 1.

Click to see the solution
  1. Define Subproblems: Let \(a_n\) be the total number of ways. Let’s consider the last segment added.
    • Case 1: The last segment is of length 3. The remaining segment has length \(n-3\). There are \(a_{n-3}\) ways.
    • Case 2: The last segment is of length 2. The remaining segment has length \(n-2\). There are \(a_{n-2}\) ways.
    • Case 3: The last segment is of length 1. The preceding segment cannot be two consecutive 1s. This is more complex.
  2. Refine Subproblems: Let \(a_n\) be the total ways. Let \(a_n^1\) be the number of ways ending with exactly one 1. Let \(a_n^{11}\) be the number of ways ending with exactly two 1s.
    • A valid partition of length \(n\) can be formed by:
      • Adding a segment of length 3 to any valid partition of length \(n-3\).
      • Adding a segment of length 2 to any valid partition of length \(n-2\).
      • Adding a segment of length 1. This can only be done if the partition of length \(n-1\) does not end in two 1s.
  3. Alternative Approach: Let \(a_n\) be the number of ways. Consider the last segment.
    • If it’s a 3, we have \(a_{n-3}\) ways.
    • If it’s a 2, we have \(a_{n-2}\) ways.
    • If it’s a 1, the previous segment could be a 2 or a 3, or a 1.
      • If the end is …2,1, we have \(a_{n-3}\) ways.
      • If the end is …3,1, we have \(a_{n-4}\) ways.
      • If the end is …1,1, the segment before that must be a 2 or a 3.
        • …2,1,1 gives \(a_{n-4}\) ways.
        • …3,1,1 gives \(a_{n-5}\) ways.
  4. Simpler Recurrence: Let \(a_n\) be the number of valid partitions. A valid partition of length \(n\) can be formed by appending:
    • a ‘3’ to a valid partition of length \(n-3\). (Number of ways: \(a_{n-3}\))
    • a ‘2’ to a valid partition of length \(n-2\). (Number of ways: \(a_{n-2}\))
    • a ‘1’ to a valid partition of length \(n-1\) that doesn’t end in ‘11’. How to count this?
    • Let’s try a direct recurrence. A valid partition must end in 2, 3, 12, 13, 112, or 113. This is too complex.
  5. Let’s go back to the first simple idea and correct it. Let \(a_n\) be the total ways.
    • Last piece is 2: \(a_{n-2}\) ways.
    • Last piece is 3: \(a_{n-3}\) ways.
    • Last piece is 1: The remaining partition of length \(n-1\) must be valid. Total ways is \(a_{n-1}\). BUT we must subtract the cases where this leads to an invalid partition. The only invalid case is appending a ‘1’ to a partition of length \(n-1\) that already ends in ‘11’. How many such partitions are there? A partition of length \(n-1\) ending in ‘11’ must have been formed from a valid partition of length \(n-3\) that did not end in ‘1’. The last piece before the ‘11’ must have been a ‘2’ or a ‘3’. This is the number of valid partitions of length \(n-4\) plus the number of valid partitions of length \(n-5\). This is getting complicated.
  6. Let’s try again:
    • \(a_n =\) (ways ending in 2) + (ways ending in 3) + (ways ending in 1)
    • \(a_n = a_{n-2} + a_{n-3} + (\text{ways ending in 1})\)
    • Ways ending in 1: must come from a partition of length \(n-1\) ending in 2 or 3, or a partition of length \(n-2\) ending in 2 or 3, followed by a 1.
    • Let’s find the first few terms:
      • a(1): “1” (1 way)
      • a(2): “2”, “11” (2 ways)
      • a(3): “3”, “12”, “21” (3 ways). Note “111” is forbidden.
      • a(4): “13”, “22”, “31”, “112”, “121”, “211” (6 ways)
      • a(5): “23”, “32”, “113”, “122”, “212”, “1121”, “1211”, “2112”, “221”, “311”, “32” (11 ways).
    • The sequence 1, 2, 3, 6, 11… requires a recurrence relation. Let \(a_n\) be the total number of ways. We can break this into cases based on the last digit(s).
    • Let \(b_n\) be ways not ending in 1. Then \(b_n = a_{n-2} + a_{n-3}\).
    • Let \(c_n\) be ways ending in 1. Then \(a_n = b_n + c_n\).
    • \(c_n\) is formed by adding 1 to a partition of \(n-1\) not ending in ‘11’. A partition of \(n-1\) ends in ‘11’ if it came from a partition of \(n-3\) not ending in ‘1’, which is \(b_{n-3}\).
    • So, \(c_n = a_{n-1} - b_{n-3} = a_{n-1} - (a_{n-5}+a_{n-6})\).
  7. Final Attempt:
    • \(a_n\): Total ways for length \(n\).
    • A valid sequence can be obtained by:
      1. Appending a ‘2’ to any valid sequence of length \(n-2\). (Ways: \(a_{n-2}\))
      2. Appending a ‘3’ to any valid sequence of length \(n-3\). (Ways: \(a_{n-3}\))
      3. Appending a ‘1’ to a valid sequence of length \(n-1\) which does not end in ‘11’.
    • How many valid sequences of length \(n-1\) end in ‘11’? A sequence of length \(n-1\) ending in ‘11’ must have come from a valid sequence of length \(n-3\) by appending ‘11’. That sequence of length \(n-3\) must not end in ‘1’. The number of ways to form a sequence of length \(k\) not ending in ‘1’ is the number of ways to form it ending in ‘2’ or ‘3’, which is \(a_{k-2}+a_{k-3}\).
    • This is not the intended simple path. Let’s try the most direct recurrence.
    • \(a_n = a_{n-1} + a_{n-2} + a_{n-3}\). This is for partitions into 1,2,3 with no restrictions.
    • With the restriction, a sequence ending in ‘111’ is forbidden.
    • \(a_n = a_{n-1} (\text{add 1}) + a_{n-2} (\text{add 2}) + a_{n-3} (\text{add 3})\). The problem is in the first term.
    • Ways to add a 1: The previous sequence of length \(n-1\) cannot end in ‘11’.
    • Number of sequences of length \(n-1\) that end in ‘11’: These must come from a valid sequence of length \(n-3\) by adding ‘11’. Any valid sequence of length \(n-3\) is fine. So there are \(a_{n-3}\) such sequences.
    • So, number of valid ways to add a ‘1’ is \(a_{n-1} - a_{n-3}\).
    • This gives the recurrence: \(a_n = (a_{n-1} - a_{n-3}) + a_{n-2} + a_{n-3} = a_{n-1} + a_{n-2}\).
  8. Find Initial Conditions:
    • \(a_1 = 1\) (“1”)
    • \(a_2 = 2\) (“2”, “11”)
    • \(a_3 = 3\) (“3”, “12”, “21”)
    • Check: \(a_3 = a_2+a_1 = 2+1=3\). Correct.
Answer: The recurrence relation is \(a_n = a_{n-1} + a_{n-2}\) with initial conditions \(a_1=1, a_2=2\).
4.6. Formulate a Recurrence for Bitstrings without Consecutive Ones (Lab 7, Task 6)

What is the number of bitstrings of length \(n\), consisting of zeros and ones, in which no two ones are consecutive?

Click to see the solution
  1. Define Subproblems: Let \(F(n)\) be the total number of valid bitstrings of length \(n\). To find a recurrence, we can count the strings based on their last digit.
    • Let \(F_0(n)\) be the number of valid bitstrings of length \(n\) that end in a 0.
    • Let \(F_1(n)\) be the number of valid bitstrings of length \(n\) that end in a 1.
  2. Formulate Relationships:
    • The total number is the sum of the two types: \(F(n) = F_0(n) + F_1(n)\).
    • A valid string of length \(n\) ending in 0 can be formed by appending a ‘0’ to any valid string of length \(n-1\). Therefore, \(F_0(n) = F(n-1)\).
    • A valid string of length \(n\) ending in 1 can only be formed by appending a ‘1’ to a valid string of length \(n-1\) that ends in a ‘0’. Therefore, \(F_1(n) = F_0(n-1)\).
  3. Combine to a Single Recurrence:
    • Substitute the relationships into the total sum: \(F(n) = F(n-1) + F_0(n-1)\).
    • We know that \(F_0(n-1) = F(n-2)\).
    • This gives the Fibonacci recurrence relation: \(F(n) = F(n-1) + F(n-2)\).
  4. Find Initial Conditions:
    • For \(n=1\): “0”, “1”. So \(F(1) = 2\).
    • For \(n=2\): “00”, “01”, “10”. So \(F(2) = 3\).
    • (Note: These are the standard Fibonacci numbers, but shifted. \(F(n) = f_{n+2}\)).
Answer: The recurrence relation is \(F(n) = F(n-1) + F(n-2)\) with initial conditions \(F(1)=2, F(2)=3\).
4.7. Rewrite a System of Recurrence Relations (Lab 7, Task 7)

Rewrite the following recursive system as a single second-order recurrence for \(a_n\): \[ \begin{cases} a_{n+1} = a_n + b_n \\ b_{n+1} = a_n - b_n \end{cases} \]

Click to see the solution
  1. Isolate \(b_n\): From the first equation, we can write \(b_n = a_{n+1} - a_n\).
  2. Advance the Index: Since the equations hold for any \(n\), they also hold for \(n+1\). The first equation becomes:
    • \(a_{n+2} = a_{n+1} + b_{n+1}\).
  3. Substitute to Eliminate \(b_{n+1}\): Use the second original equation, \(b_{n+1} = a_n - b_n\), to replace \(b_{n+1}\) in the equation from step 2.
    • \(a_{n+2} = a_{n+1} + (a_n - b_n)\).
  4. Substitute to Eliminate \(b_n\): Now use the expression from step 1, \(b_n = a_{n+1} - a_n\), to replace the remaining \(b_n\).
    • \(a_{n+2} = a_{n+1} + a_n - (a_{n+1} - a_n)\).
  5. Simplify:
    • \(a_{n+2} = a_{n+1} + a_n - a_{n+1} + a_n = 2a_n\).
Answer: The single second-order recurrence for \(a_n\) is \(a_{n+2} = 2a_n\).
4.8. Represent a Sum Recursively (Tutorial 7, Task 1)

Represent the sum \(S(n) = \sum_{i=1}^{n} i = 1+2+\cdots+n\) recursively.

Click to see the solution
  1. Define the Base Case: The sum for \(n=1\) is the starting point.
    • \(S(1) = 1\).
  2. Find the Recursive Step: Express the sum for \(n+1\) in terms of the sum for \(n\).
    • \(S(n+1) = 1+2+\cdots+n+(n+1)\).
    • The first \(n\) terms are equal to \(S(n)\).
    • \(S(n+1) = S(n) + (n+1)\).
Answer: The recursive representation is \(S(1) = 1\), \(S(n+1) = S(n) + n+1\).
4.9. Represent a Sum using a Known Function (Tutorial 7, Task 2)

Represent the sum \(\sum_{i=15}^{n+3} i\) using the function \(S(n) = \sum_{i=1}^{n} i\).

Click to see the solution
  1. Express as a Difference of Sums: The sum from 15 to \(n+3\) can be found by taking the sum from 1 to \(n+3\) and subtracting the sum of the terms we don’t want, which are the terms from 1 to 14.
  2. Write the formula:
    • \(\sum_{i=15}^{n+3} i = (1+\cdots+(n+3)) - (1+\cdots+14)\).
  3. Use the function S(n):
    • The first part is the sum up to \(n+3\), which is \(S(n+3)\).
    • The second part is the sum up to 14, which is \(S(14)\).
Answer: The representation is \(S(n+3) - S(14)\).
4.10. Represent Factorial Recursively (Tutorial 7, Task 3)

Represent the factorial function \(n! = \prod_{i=1}^{n} i\) recursively.

Click to see the solution
  1. Define the Base Case: The factorial for \(n=1\) is the starting point.
    • \(1! = 1\). (Often, the base case is defined as \(0! = 1\)).
  2. Find the Recursive Step: Express the factorial of \(n+1\) in terms of the factorial of \(n\).
    • \((n+1)! = 1 \cdot 2 \cdots n \cdot (n+1)\).
    • The product of the first \(n\) terms is equal to \(n!\).
    • \((n+1)! = n! \cdot (n+1)\).
Answer: The recursive representation is \(1! = 1\), \((n+1)! = (n+1)n!\).
4.11. Represent a Product using Factorials (Tutorial 7, Task 4)

Represent the product \(\prod_{i=4000}^{n+2} i\) using the factorial function \(n! = \prod_{i=1}^{n} i\).

Click to see the solution
  1. Express as a Quotient of Products: The product from 4000 to \(n+2\) can be found by taking the full product from 1 to \(n+2\) and dividing by the product of the terms we don’t want, which are the terms from 1 to 3999.
  2. Write the formula:
    • \(\prod_{i=4000}^{n+2} i = 4000 \cdot 4001 \cdots (n+2)\).
    • \(= \frac{1 \cdot 2 \cdots 3999 \cdot 4000 \cdots (n+2)}{1 \cdot 2 \cdots 3999}\).
  3. Use the factorial function:
    • The numerator is the product up to \(n+2\), which is \((n+2)!\).
    • The denominator is the product up to 3999, which is \(3999!\).
Answer: The representation is \(\frac{(n+2)!}{3999!}\).
4.12. Solve a Recurrence Sequence (Tutorial 7, Task 5)

Solve the recurrence sequence: \(a_1 = -1\), \(a_{n+1} = -a_n\).

Click to see the solution
  1. Write the Characteristic Equation: The recurrence \(a_{n+1} + a_n = 0\) corresponds to the characteristic equation \(\lambda + 1 = 0\).
  2. Find the Root: The root is \(\lambda = -1\).
  3. Write the General Solution: The general solution is of the form \(a_n = c \cdot (\lambda)^n = c(-1)^n\).
  4. Use the Initial Condition to Find c: We are given \(a_1 = -1\).
    • \(-1 = c(-1)^1 = -c\).
    • This gives \(c = 1\).
  5. Write the Final Answer: Substitute the value of c back into the general solution.
    • \(a_n = 1 \cdot (-1)^n = (-1)^n\).
Answer: \(a_n = (-1)^n\).
4.13. Solve a Recurrence Sequence (Tutorial 7, Task 6)

Solve the recurrence sequence: \(a_0 = 3\), \(a_{n+1} = 2a_n\).

Click to see the solution
  1. Write the Characteristic Equation: The recurrence \(a_{n+1} - 2a_n = 0\) corresponds to the characteristic equation \(\lambda - 2 = 0\).
  2. Find the Root: The root is \(\lambda = 2\).
  3. Write the General Solution: The general solution is of the form \(a_n = c \cdot (\lambda)^n = c \cdot 2^n\).
  4. Use the Initial Condition to Find c: We are given \(a_0 = 3\).
    • \(3 = c \cdot 2^0 = c \cdot 1\).
    • This gives \(c = 3\).
  5. Write the Final Answer: Substitute the value of c back into the general solution.
    • \(a_n = 3 \cdot 2^n\).
Answer: \(a_n = 3 \cdot 2^n\).
4.14. Solve a Recurrence Sequence (Tutorial 7, Task 7)

Solve the recurrence sequence: \(a_0 = 2, a_1 = -1, a_{n+2} = a_n\).

Click to see the solution
  1. Write the Characteristic Equation: The recurrence \(a_{n+2} - a_n = 0\) corresponds to the characteristic equation \(\lambda^2 - 1 = 0\).
  2. Find the Roots: The roots are \(\lambda_1 = 1\) and \(\lambda_2 = -1\).
  3. Write the General Solution: The general solution is of the form \(a_n = c_1(\lambda_1)^n + c_2(\lambda_2)^n = c_1(1)^n + c_2(-1)^n\).
  4. Use the Initial Conditions to Find Constants:
    • For \(n=0\): \(a_0 = 2 = c_1(1)^0 + c_2(-1)^0 \implies 2 = c_1 + c_2\).
    • For \(n=1\): \(a_1 = -1 = c_1(1)^1 + c_2(-1)^1 \implies -1 = c_1 - c_2\).
  5. Solve the System:
    • Adding the two equations: \(2 + (-1) = (c_1+c_1) + (c_2-c_2) \implies 1 = 2c_1 \implies c_1 = 1/2\).
    • Substitute back: \(2 = 1/2 + c_2 \implies c_2 = 3/2\).
  6. Write the Final Answer:
    • \(a_n = \frac{1}{2}(1)^n + \frac{3}{2}(-1)^n\).
Answer: \(a_n = \frac{1 + 3(-1)^n}{2}\).
4.15. Solve a Recurrence Sequence (Tutorial 7, Task 8)

Solve the recurrence sequence: \(a_0 = 1, a_1 = 0, a_{n+2} = 2a_{n+1} - a_n\).

Click to see the solution
  1. Write the Characteristic Equation: The recurrence \(a_{n+2} - 2a_{n+1} + a_n = 0\) corresponds to the characteristic equation \(\lambda^2 - 2\lambda + 1 = 0\).
  2. Find the Roots: The equation is \((\lambda-1)^2 = 0\). We have a repeated root \(\lambda_1 = \lambda_2 = 1\).
  3. Write the General Solution: For a repeated root, the general solution is \(a_n = (c_1 + c_2n)\lambda^n = (c_1 + c_2n)(1)^n = c_1 + c_2n\).
  4. Use the Initial Conditions to Find Constants:
    • For \(n=0\): \(a_0 = 1 = c_1 + c_2(0) \implies c_1 = 1\).
    • For \(n=1\): \(a_1 = 0 = c_1 + c_2(1) \implies 0 = 1 + c_2 \implies c_2 = -1\).
  5. Write the Final Answer:
    • \(a_n = 1 - 1 \cdot n = 1 - n\).
Answer: \(a_n = 1 - n\).
4.16. Formulate a Recurrence Relation (Tutorial 7, Task 9)

Formulate a recurrence relation and provide initial conditions for the number of binary sequences of length \(n\) over the alphabet \(\{0,1\}\) that do not contain two consecutive zeros or two consecutive ones.

Click to see the solution
  1. Define Subproblems: Let \(a_n\) be the total number of valid sequences of length \(n\). To find a recurrence, we can count the sequences based on their last digit.
    • Let \(b_n\) be the number of valid sequences of length \(n\) that end in a 0.
    • Let \(c_n\) be the number of valid sequences of length \(n\) that end in a 1.
  2. Formulate Relationships:
    • The total number of sequences is \(a_n = b_n + c_n\).
    • If a sequence of length \(n\) ends in a 0, the preceding character must have been a 1. This means it was formed by appending a 0 to a valid sequence of length \(n-1\) that ended in a 1. Thus, \(b_n = c_{n-1}\).
    • Similarly, if a sequence of length \(n\) ends in a 1, the preceding character must have been a 0. Thus, \(c_n = b_{n-1}\).
  3. Combine to a Single Recurrence:
    • \(a_n = b_n + c_n = c_{n-1} + b_{n-1} = a_{n-1}\). This is incorrect.
    • Let’s re-evaluate: A valid sequence of length \(n\) ending in 0 is an extension of any valid sequence of length \(n-1\) ending in 1. So \(b_n = c_{n-1}\).
    • A valid sequence of length \(n\) ending in 1 is an extension of any valid sequence of length \(n-1\) ending in 0. So \(c_n = b_{n-1}\).
    • The problem is that the sequences are alternating. Let’s find the first few terms manually.
      • \(n=1\): 0, 1 (Total \(a_1=2\))
      • \(n=2\): 01, 10 (Total \(a_2=2\))
      • \(n=3\): 010, 101 (Total \(a_3=2\))
  4. Conclusion: For any length \(n \ge 1\), there are only two such sequences: one starting with 0 (e.g., 01010…) and one starting with 1 (e.g., 10101…). The recurrence relation is simply \(a_n = 2\) for \(n \ge 1\).
Answer: The initial condition is \(a_1=2\). The recurrence relation is \(a_n = 2\) for all \(n \ge 1\).
4.17. Rewrite a System of Recurrence Relations (Tutorial 7, Task 10)

Rewrite the following system of recurrence relations as a single second-order recurrence for \(a_n\): \[ \begin{cases} a_{n+1} = a_n + b_n \\ b_{n+1} = a_n - b_n \end{cases} \]

Click to see the solution
  1. Isolate \(b_n\): From the first equation, we can write \(b_n = a_{n+1} - a_n\).
  2. Advance the Index: Since the equations hold for any \(n\), they also hold for \(n+1\).
    • \(a_{n+2} = a_{n+1} + b_{n+1}\).
  3. Substitute to Eliminate \(b_{n+1}\): Use the second original equation to replace \(b_{n+1}\).
    • \(a_{n+2} = a_{n+1} + (a_n - b_n)\).
  4. Substitute to Eliminate \(b_n\): Now use the expression from step 1 to replace \(b_n\).
    • \(a_{n+2} = a_{n+1} + a_n - (a_{n+1} - a_n)\).
  5. Simplify:
    • \(a_{n+2} = a_{n+1} + a_n - a_{n+1} + a_n = 2a_n\).
Answer: The single second-order recurrence for \(a_n\) is \(a_{n+2} = 2a_n\).